package tree.VerifySearchTree;

import tree.TreeNode;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @ClassName VerifySearchTree
 * @Description TODO
 * @Author lenovo
 * @Date 2023-03-30 9:37
 * @Version 1.0
 * @Comment Magic. Do not touch.
 * If this comment is removed. the program will blow up
 */
public class VerifySearchTree {

    /**
     * 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
     * <p>
     * 有效 二叉搜索树定义如下：
     * <p>
     * 节点的左子树只包含 小于 当前节点的数。
     * 节点的右子树只包含 大于 当前节点的数。
     * 所有左子树和右子树自身必须也是二叉搜索树
     *
     * @param root
     * @return
     */
    public boolean isValidBST(TreeNode root) {

        if (root == null) return true;
        return DFS(root);
    }

    private boolean DFS(TreeNode root) {
        if (root == null) return true;

        if (root.left != null && root.left.val >= root.val) {
            return false;
        }
        if (root.right != null && root.right.val <= root.val) {
            return false;
        }
        return DFS(root.left) && DFS(root.right);
    }

    //   2
    // 1    5
    //    1   6
    public boolean isValidBST1(TreeNode root) {
        return dfss(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }

    private boolean dfss(TreeNode root, int minValue, int maxValue) {
        if (root == null) return true;

        if (root.val <= minValue || root.val >= maxValue) {
            return false;
        }
        return dfss(root.left, minValue, root.val) && dfss(root.right, root.val, maxValue);
    }


    public boolean isValidBST2(TreeNode root) {
        if (root == null) return true;

        Queue<TreeNode> treeNodeQueue = new LinkedList<>();

        treeNodeQueue.add(root);

        while (!treeNodeQueue.isEmpty()) {
            int size = treeNodeQueue.size();
            while (size > 0) {
                TreeNode poll = treeNodeQueue.poll();
                if ((poll.left != null && poll.val <= poll.left.val) || (poll.right != null && poll.val >= poll.right.val)) {
                    return false;
                }

                if (poll.left != null) treeNodeQueue.add(poll.left);
                if (poll.right != null) treeNodeQueue.add(poll.right);
                size--;
            }
        }
        return true;
    }

    //todo
    public boolean isValidBST3(TreeNode root) {
        if (root == null) {
            return true;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode pre = null;
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;// 左
            }
            // 中，处理
            TreeNode pop = stack.pop();
            if (pre != null && pop.val <= pre.val) {
                return false;
            }
            pre = pop;

            root = pop.right;// 右
        }
        return true;
    }

    //   2
    // 1    3
    //    1   6
    public static void main(String[] args) {
        VerifySearchTree verifySearchTree = new VerifySearchTree();
        TreeNode root = new TreeNode(2);
        TreeNode left = new TreeNode(1);
        TreeNode right = new TreeNode(5);
        root.left = left;
        root.right = right;
        TreeNode right1 = new TreeNode(1);
        TreeNode right2 = new TreeNode(6);
        right.left = right1;
        right.right = right2;

        System.out.println(verifySearchTree.isValidBST1(root));
    }
}